#!/usr/bin/env python
# -*- coding:utf-8 -*-

import nltk 
import re 
from nltk.corpus import brown
import pprint

# 4. 编写结构化程序
# 4.1 基础
# 赋值
"""
foo = 'Monty'
bar = foo
foo = 'Python'
print(bar)

foo1 = ['Monty','Python']
bar = foo1 
print(bar)
foo1[1] = 'Bodkin'
print(bar)
print(foo1)
print('-='*20)
empty = []
nested = [empty,empty,empty]
print(nested)
nested[1].append('Python')
print(nested)
# 这三个元素中的每一个都只是一个内存中的同一链表的引用.

print('=-'*20)
# id()函数找出任一对象的数字标识符.
nested = [[]] * 3
nested[1].append('Python')
nested[1] = ['Monty']
print(nested)


# 赋值链表中的对象引用
bar = foo[:]

# 复制结构,而不复制任何对象引用使用copy.deepcopy()
"""




# 等式
# is 操作符测试对象的标识符
"""
size = 5
python = ['Python']
snake_nest = [python] * size 
print(snake_nest[0] == snake_nest[1] == snake_nest[2] == snake_nest[3] == snake_nest[4])
print(snake_nest[0] is snake_nest[1] is snake_nest[2] is snake_nest[3] is snake_nest[4])

import random
position = random.choice(range(size))
snake_nest[position] = ['Python']
print(snake_nest)
print(snake_nest[0] == snake_nest[1] == snake_nest[2] == snake_nest[3] == snake_nest[4])
print(snake_nest[0] is snake_nest[1] is snake_nest[2] is snake_nest[3] is snake_nest[4])

print([id(snake) for snake in snake_nest])
"""




# 条件语句
# 一个非空字符串或链表被判定为真,而一个空字符串或链表的被判定为假.
"""
mixed = ['cat','',['dog'],[]]
for element in mixed:
    if element:
        print(element)

animals = ['cat','dog']
if 'cat' in animals:
    print(1)
elif 'dog' in animals:
    print(2)
"""


# 4.2 序列
# 序列对象: 字符串和链表
# 另一种序列被称为元组,元组由逗号操作符构造,通常使用括号括起来.
# 元组可以被索引和切片.
"""
t = 'walk','fem',3
print(t)
print(t[0])
print(t[1:])
print(len(t))
print('--='*20)
# 元组使用逗号操作符来构造.
raw = 'I turned off the spectroroute'
text = ['I','turned','off','the','spectroroute']
pair = (6,'turned')
print(raw[2],text[3],pair[1])
print(raw[-3:],text[-3:],pair[-3:])
print(len(raw),len(text),len(pair))
"""



# 获得无重复的逆序排列的s的元素: 使用reversed(sorted(set(s)))
"""
raw = 'Red lorry,yellow lorry,red lorry, yellow lorry.'
text = nltk.word_tokenize(raw)
fdist = nltk.FreqDist(text)
print(list(fdist))
for key in fdist:
    print(fdist[key],)

"""


# 使用元组安排链表内容
"""
words = ['I','turned','off','the','spectroroute']
words[2],words[3],words[4] = words[3],words[4],words[2]
print(words)

tmp = words[2]
words[2] = words[3]
words[3] = words[4]
words[4] = tmp
"""

# 序列处理函数: sorted()和reversed()
# zip()取两个或两个以上的序列中的项目,将它们压缩打包成单个的配对链表.
# 给定一个序列s,enumerate(s) 返回一个包含索引和索引处项目的配对.
"""
words = ['I','turned','off','the','spectroroute']
tags = ['noun','verb','prep','det','noun']
print(zip(words,tags))
print(list(enumerate(words)))
"""



# 指定想要分割数据的位置,然后再这个位置分割序列
"""
text = nltk.corpus.nps_chat.words()
cut = int(0.9 * len(text))
training_data, test_data = text[:cut],text[cut:]
text == training_data + test_data
print(len(training_data) / len(test_data))
"""




# 合并不同类型的序列
# 用链表推导处理一个字符串中的词,按长度排序
"""
words = 'I turned off the spectroroute'.split()
wordlens = [(len(word),word) for word in words]
print(wordlens.sort())
print(' '.join(w for (_,w) in wordlens))
"""
"""
使用链表推导建立一个元组的链表,其中每个元组由一个数字(词长)和这个词组成.
使用sort()方法就地排序链表. 
最后,丢弃长度信息,并将这些词连接会一个字符串.

列表是可变的,元组不可变.
列表可以被修改,元组不能修改.
"""
# 用一个链表表示词典,是一个单一类型的对象的集合.
"""
lexicon = [
    ('the','det',['Di:','D@']),
    ('off','prep',['Qf','O:f'])
]
lexicon.sort()
lexicon[1] = ('turned','VBD',['t3:nd','t3`nd'])
del lexicon[0]
print(lexicon)
# 使用lexicon = tuple(lexicon)将词典转换为一个元组.
"""




# 产生器表达式
# 分词和规范化一个文本
text = """When I use a word,"Humpty Dumpty said in rather a scornful tone,
    "it means just what I choose it to mean - neither more nor less."""
"""
print([w.lower() for w in nltk.word_tokenize(text)])

# 链表对象的存储空间在max()的值被计算之前分配.
print(max([w.lower() for w in nltk.word_tokenize(text)]))

# 数据流向它的函数,由于调用的函数只是要找最大值--按字典顺序排在最后的词--它可以处理数据流,而无需存储最大值以外的任何值.
print(max(w.lower() for w in nltk.word_tokenize(text)))
"""



# 4.3 风格问题
"""
缩进使用4个空格.
每行应少于80个字符长. 可以在圆括号,方括号或花括号内换行.
在行尾需要换行的地方添加一个反斜杠.
"""
"""
rotokas_words = nltk.corpus.toolbox.words('rotokas.dic')
cv_word_pairs = [(cv,w) for w in rotokas_words 
        for cv in re.findall('[ptksvr][aeiou]',w)]
cfd = nltk.ConditionalFreqDist(
        (genre,word)
        for genre in brown.categories()
        for word in brown.words(categories=genre))
print(rotokas_words)    
print(cv_word_pairs)
print(cfd)

ha_words = ['aaahhhh','ah','ahah','ahahah','ahh','ahhahahaha',
        'ahhh','ahhhh','ahhhhhh','ahhhhhhhhhhhh','ha','haaa',
        'hah','haha','hahaaa','hahah','hahaha']
"""    
# 在圆括号,方括号或大括号中换行.或者在行尾换行时添加一个反斜杠.





# 过程风格和声明风格
"""
tokens = nltk.corpus.brown.words(categories='news')
count = 0  # 标识符的数量
total = 0  # 储存所有词的长度的总和
for token in tokens:
    count += 1
    total += len(token)
print(total / count)


# 使用生成器表达式累加标识符的长度
total = sum(len(t) for t in tokens)
print(total / len(tokens))  # 计算平均值.
"""





"""
使用enumerate()处理序列s,为s中每个项目产生一个(i,s[i])形式的元组,以(0,s[0])开始.
枚举频率分布的值,捕获变量rank和word中的整数--字符串对.
按照产生排序项列表时的需要,输出rank+1使计数从1开始.
"""
"""
fd = nltk.FreqDist(nltk.corpus.brown.words())
cumulative = 0.0
for rank, word in enumerate(fd):
    cumulative += fd[word] * 100 / fd.N()
    print("%3d %6.2f%% %s" % (rank+1,cumulative,word))
    if cumulative > 25:
        break



# 使用循环变量存储最大值或最小值.找出文本中最长的词.
text = nltk.corpus.gutenberg.words('milton-paradise.txt')
longest = ''
for word in text:
    if len(word) > len(longest):
        longest = word

print(longest)
"""




# 使用两个链表推导
"""
# 第一个解决方案是找到第一个长度最长的词.
maxlen = max(len(word) for word in text)
print(maxlen)
# 第二种方案找到所有最长的词.
print([word for word in text if len(word) == maxlen])
"""





# 计数器的合理用途
# 链表推导中使用循环变量
"""
sent = ['The','dog','gave','John','the','newspaper']
n = 3
print([sent[i:i+n] for i in range(len(sent)-n+1)])
"""



"""
使用循环变量构建多维结构。 
建立一个m行n列的数组,其中每个元素是一个集合.
使用一个嵌套的链表推导.
"""
"""
m,n = 3,7
array = [[set() for i in range(n)] for j in range(m)]
array[2][5].add('Alice')
pprint.pprint(array)
"""


# 4.4 函数: 结构化编程的基础
# 函数输入和输出
"""
def repeat(msg,num):
    return ' '.join([msg] * num)

monty = 'Monty Python'
print(repeat(monty,3))

def Monty():
    return "Monty Yuan"

print(Monty())
# 函数会通过return语句将其结果返回给调用它的程序.
print(repeat(Monty(),3))
print(repeat('Monty Yuanjie',3))
"""

# 一般情况下,函数应该修改参数的内容或返回一个值.
"""
def my_sort1(mylist):
    mylist.sort()

def my_sort2(mylist):
    return sorted(mylist)
"""




# 参数传递
"""
def set_up(word,properties):
    word = 'lolcat'
    properties.append('noun')
    properties = 5

w = ''
p = []
print(set_up(w,p))
print(w)
print(p)
"""



# 变量的作用域
"""
函数定义为变量创建了一个新的局部的范围.

在一个函数体内部使用一个现有的名字时,Python解释器先尝试按照函数本地的
名字来解释. 如果没有发现,解释器检查它是否是一个模块内的全局名称.
如果没有成功,最后,解释器会检查是否是Python内置的名字. 
这就是名称解析的LGB规则: 本地(local), 全局(global),然后内置(built-in)

一个函数使用global声明创建一个新的全局变量.
在函数内部定义全局变量会导致上下文依赖性而限制函数的便携性.
"""



# 参数类型检查
"""
def tag(word):
    if word in ['a','the','all']:
        return 'det'
    else:
        return 'noun'

print(tag('the'))
print(tag('knight'))
print(tag(["Tis",'but','a','scratch']))


# 使用assert语句的basestring的类型一起,它是unicode和str的产生类型.
def tag(word):
    assert isinstance(word,basestring),"argument to tag() must be a string"
    if word in ['a','the','all']:
        return 'det'
    else:
        return 'noun'    

# assert语句失败,它会产生一个不可忽视的错误而停止程序执行.
# 程序中添加断言可以找到逻辑错误.
"""




# 功能分解
"""
函数可以将多个动作组合成一个单一的复杂的行动,并给它关联一个名称.
"""

# 文档说明函数: docstring.




# 4.5 关于函数
# 作为参数的函数
# Python允许传递一个函数作为另一个函数的参数.
# 传递内置函数len()或用户定义的函数last_letter()作为另一个函数的参数.
"""
sent = ['Take','care','of','the','sense',',','and','the',
        'sounds','will','take','care','of','themselves','.']

def extract_property(prop):
    return [prop(word) for word in sent]

print(extract_property(len))

def last_letter(word):
    return word[-1]

print(extract_property(last_letter))
"""
"""
对象len和last_letter可以像链表和字典那样被传递.
注意: 只有在调用该函数时,才在函数名后使用括号. 
      当只是将函数作为一个对象,括号被省略.

lambda表达式: 可定义函数来作为其他函数的参数.
"""
# print(extract_property(lambda w: w[-1]))


# 累计函数
# 这些函数以初始化一些存储开始,迭代和处理输入的数据,最后返回一些最终的对象.
# 标准方式是初始化一个空链表,累计材料,然后返回这个链表.
# 累计输出到一个链表
"""
def search1(substring,words):
    result = []
    for word in words:
        if substring in word:
            result.append(word)
    return result

def search2(substring,words):
    for word in words:
        if substring in word:
            yield word

print("search1:")
for item in search1('zz',nltk.corpus.brown.words()):
    print(item)
print("search2:")
for item in search2('zz',nltk.corpus.brown.words()):
    print(item)
"""
"""
说明: 
    函数search2()是一个产生器. 第一次调用此函数,它运行到yield语句然后停下来.
    调用程序获得第一个词,没有任何处理. 一旦调用程序对另一个词做好准备,
    函数会从停下来的地方继续执行,直到再次遇到yield语句. 这种方法更有效.
    因为函数只产生调用程序需要的数据,并不需要分配额外的内存来存储输出.
"""

# 产生一个词链表的所有排列. 强制permutations()函数产生所有它的输出,将它包装载list()调用中.
"""
def permutations(seq):
    if len(seq) <= 1:
        yield seq 
    else:
        for perm in permutations(seq[1:]):
            for i in range(len(perm)+1):
                yield perm[:i] + seq[0:1] + perm[i:]

print(list(permutations(['police','fish','buffalo'])))
# permutations函数使用了一种技术叫递归.
"""






# 高阶函数
"""
从定义一个函数is_content_word()开始,它检查一个词是否来自一个开放的实词类.
使用此函数作为offilter()的第一个参数,它对作为它的第二个参数的序列中的每个项目运用该函数,
只保留该函数返回True的项目.
"""
"""
def is_content_word(word):
    return word.lower() not in ['a','of','the','and','will',',','.']

sent = ['Take','care','of','the','sense',',','and','the',
        'sounds','will','take','care','of','themselves','.']

print(filter(is_content_word,sent))
print([w for w in sent if is_content_word(w)])


# map(),将一个函数运用到一个序列中的每一项.
# 计数每个词中的元音的数量
print(map(lambda w: len(filter(lambda c: c.lower() in "aeiou",w)),sent))
print([len([c for c in w if c.lower() in "aeiou"]) for w in sent])
"""




# 参数的命名
"""
def repeat(msg='<empty>',num=1):
    return msg * num

print(repeat(num=3))
print(repeat(msg='Alice'))
print(repeat(num=5,msg='Alice'))
"""

# 定义一个函数,接受任意数量的未命名和命名参数,并通过一个就地的参数链表*args和一个就地的关键字参数字典**kwargs来访问他们.
"""
def generic(*args,**kwargs):
    print(args)
    print(kwargs)

print(generic(1,"African swallow",monty="python"))



# 当*args作为函数参数时,它实际上对应函数所有的未命名参数.
song = [['four','calling','birds'],
    ['three','French','hens'],
    ['two','turtle','doves']]
print(zip(song[0],song[1],song[2]))
print(zip(*song))


# 有三种等效的方法来调用这个函数
def freq_words(file,min=1,num=10):
    text = open(file).read()
    tokens = nltk.word_tokenize(text)
    freqdist = nltk.FreqDist(t for t in tokens if len(t) >= min)
    return freqdist.keys()[:num]

fw = freq_words('ch01.rst',4,10)
print(fw)
fw = freq_words('ch01.rst',min=4,num=10)
print(fw)
fw = freq_words('ch01.rst',num=10,min=4)
print(fw)


# 设置了verbose标志将会报告其进展情况
def freq_words(file,min=1,num=10,verbose=False):
    freqdist = FreqDist()
    if trace: print("Opening",file)
    text = open(file).read()
    if trace: print("Read in %d characters" % len(file))
    for word in nltk.word_tokenize(text):
        if len(word) >= min:
            freqdist.inc(word)
            if trace and freqdist.N() % 100 == 0: print(".")
    if trace: print 
    return freqdist.keys()[:num]
"""
"""
注意: 
    不要使用可变对象作为参数的默认值.
    这个函数的一系列调用将使用同一个对象.
"""



# 4.6 程序开发
# Python模块的结构
"""
程序模块目的是把逻辑上相关的定义和函数结合在一起,以方便重用和更高层次的抽象.
Python模块只是一些单独的.py文件.
一个模块可以包含用于创建和操纵一种特定的数据结构.
"""

# 定义一个函数来收集一个文本中给定长度的所有标识符。 
# 该函数有文本和词长作为参数,还有一个额外的参数,允许指定结果的初始值作为参数.
"""
def find_words(text,wordlength,result=[]):
    for word in text:
        if len(word) == wordlength:
            result.append(word)
    return result

# 第一次调用find_words()得到所有预期的三个字母的词.
print(find_words(['omg','teh','lolcat','sitted','on','teh','mat'],3))
# 第二次为result指定一个初始值：单元素链表['ur'],结果中有这个词连同我们文本中其他双字母的词.
print(find_words(['omg','teh','lolcat','sitted','on','teh','mat'],2,['ur']))
print(find_words(['omg','teh','lolcat','sitted','on','teh','mat'],2,['ur']))
print(find_words(['omg','teh','lolcat','sitted','on','teh','mat'],3))
"""


"""
防御性编程策略是要清楚表述你的代码,选择有意义的变量和函数名,
并通过将代码分解成拥有良好文档的接口的函数和模块尽可能的简化代码.
"""




# 4.7 算法设计
# 递归
"""
假设有n个词,要计算出它们结合在一起有多少不同的方式能组成一个词序列.
如果只有一个词(n=1),只是一种方式组成一个序列. 如果有2个词,就有2种方式
将它们组成一个序列. 3个字有6种可能性. 一般n个词有n* n - 1
"""
"""
# 使用迭代.
def factoriall(n):
    result = 1
    for i in range(n):
        result *= (i+1)
    return result

print(factoriall(10))


# 为n-1个不同的词构建所有的排列,有n个地方可以插入一个新词:开始,结束或任意两个词之间的n-2个空隙.将n-1个词的解决方案数乘以n的值.
# 使用递归.
def factorial2(n):
    if n == 1:
        return 1 
    else:
        return n * factorial2(n-1)
"""

# 用递归处理深层嵌套的对象.
"""
def size1(s):
    return 1 + sum(size1(child)for child in s.hyponyms())

def size2(s):
    layer = [s] # 同义词集本身.
    total = 0
    while layer:
        total += len(layer) # 同义词集的总数
        layer = [h for c in layer for h in c.hyponyms()]
    return total

from nltk.corpus import wordnet as wn 
dog = wn.synset('dog.n.01')
print(size1(dog))
print(size2(dog))



# 构建一个字母查找树: 一个递归函数建立一个嵌套的字典结构,每一级嵌套包含给定前缀的所有单词,子查找树含有所有可能的后续词.
def insert(trie,key,value):
    if key:
        first, rest = key[0],key[1:]
        if first not in trie:
            trie[first] = {}
        insert(trie[first],rest,value)
    else:
        trie['value'] = value 

trie = nltk.defaultdict(dict)
print(insert(trie,'chat','cat'))
print(insert(trie,'chien','dog'))
print(insert(trie,'chair','flesh'))
print(insert(trie,'chic','stylish'))
trie = dict(trie)  
print(trie['c']['h']['a']['t']['value'])
pprint.pprint(trie)
"""






# 权衡空间与时间
# 通过索引文档集合,它提供更快的查找.
# 一个简单的全文检索系统
"""
def raw(file):
    contents = open(file).read()
    contents = re.sub(r'<.*?>',' ',contents)
    contents = re.sub('\s+',' ',contents)
    return contents

def snippet(doc,term):
    text = ' '*30 + raw(doc) + ' '*30
    pos = text.index(term)
    return text[pos-30:pos+30]

print("Building Index...")
files = nltk.corpus.movie_reviews.abspaths()

idx = nltk.Index((w,f) for f in files for w in raw(f).split())
query = ''
while query != "quit":
    query = input("query>")
    if query in idx:
        for doc in idx[query]:
            print(snippet(doc,query))
    else:
        print("Not found")

# 为语料库创建一个词汇表,每个词都被存储一次的链表,然后转化这个链表通过查找任意词来找到它的标识符.
# 每个文档都进行预处理,使一个词链表变成一个整数链表.

# 预处理已标注的语料库数据,将所有的词和标注转换成整数.
def preprocess(tagged_corpus):
    words = set()
    tags = set()
    for sent in tagged_corpus:
        for word, tag in sent:
            words.add(word)
            tag.add(tag)
    
    wm = dict((w,i) for (i,w) in enumerate(words))
    tm = dict((t,i) for (i,t) in enumerate(words))
    return [[(wm[w],tm[t]) for (w,t) in sent] for sent in tagged_corpus]
"""


"""
空间时间权衡例子是维护一个词汇表. 
如果你需要处理一段输入文本检查所有的词是否在现有的词汇表中,词汇表应存储为一个集合。
集合中的元素会自动索引。
"""





"""
动态规划:
   用于解决包含多个重叠的子问题的问题.
   将计算结果存储在一个查找表中.
"""
# 四种方法计算梵文旋律:1 迭代,2 自底向上的动态规划 3. 自上而下的动态规划. 4. 内置默记法
def virahanka1(n):
    if n == 0:
        return [""]
    elif n == 1:
        return ["S"]
    else:
        s = ["S" + prosody for prosody in virahanka1(n-1)]
        l = ["L" + prosody for prosody in virahanka1(n-2)]
        return s + l

def virahanka2(n):
    # virahanka2是自下而上的方法进行动态规划.
    # 解决较大问题前先解决较小的问题.

    lookup = [[""],["S"]]
    for i in range(n-1):
        s = ["S" + prosody for prosody in lookup[i+1]]
        l = ["L" + prosody for prosody in lookup[i]]
        lookup.append(s + l)
    return lookup[n]


def virahanka3(n,lookup={0:[""],1:["S"]}):
    if n not in lookup:
        s = ["S" + prosody for prosody in virahanka3(n-1)]
        l = ["L" + prosody for prosody in virahanka3(n-2)]
        lookup[n] = s + l
    return lookup[n]
from nltk import memoize
@memoize
def virahanka4(n):
    if n == 0:
        return [""]
    elif n == 1:
        return ["S"]
    else:
        s = ["S" + prosody for prosody in virahanka4(n-1)]
        l = ["L" + prosody for prosody in virahanka4(n-2)]
        return s + l
    
print(virahanka1(4))
print(virahanka2(4))
print(virahanka3(4))
print(virahanka4(4))
